package com.arron.algorithm.leetcodetop100.动态规划;

import java.util.*;

/**
 * 回溯解法：
 *
 * @see com.arron.algorithm.leetcodetop100.回溯.单词拆分
 */
public class 单词拆分 {


    Set<String> wordDictSet;
    Boolean[] dp;

    public boolean wordBreak(String s, List<String> wordDict) {

        wordDictSet = new HashSet<>(wordDict);
        dp = new Boolean[s.length()+1];

        return matchPrefix_plus(s, 0);
    }

    public boolean matchPrefix_plus(String s, int start) {

        if (dp[start] != null){
            return dp[start];
        }

        if (start == s.length()) {
            dp[start] = true;
            return dp[start];
        }


        for (int len = 1; len <= s.length()-start; len++) {

            String prefix = s.substring(start, start + len);
            if (wordDictSet.contains(prefix) && matchPrefix_plus(s, start + len)) {
                dp[start] = true;
                return dp[start];
            }
        }
        dp[start] = false;
        return dp[start];
    }

    public boolean matchPrefix(String s, int start) {

        if (start == s.length()) {
            return true;
        }


        for (int len = 1; len <= s.length()-start; len++) {

            String prefix = s.substring(start, start + len);
            if (wordDictSet.contains(prefix) && matchPrefix(s, start + len)) {
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) {
        String s = "aaaaaab";
        List<String> strings = new ArrayList<>(Arrays.asList("a","aa","aaa","aaaa","aaaaa","aaaaaa"));

        单词拆分 wordBreak = new 单词拆分();
        System.out.println(wordBreak.wordBreak(s, strings));

    }


}
